package linked_list

import (
	"bytes"
	"fmt"
)

// 双向循环链表
type DoublyLinkedList struct {
	dummyHead *node
	size      int
	dummyTail *node
}

type node struct {
	val  interface{}
	next *node
	prev *node
}

func NewDoublyLinkedList() *DoublyLinkedList {
	dummyHead := &node{}
	dummyTail := &node{}
	dummyHead.next = dummyTail
	dummyTail.prev = dummyHead
	return &DoublyLinkedList{
		dummyHead: dummyHead,
		size:      0,
		dummyTail: dummyTail,
	}
}

// 在指定位置添加对应的元素
func (dll *DoublyLinkedList) Add(index int, e interface{}) {
	cur := dll.dummyHead
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	curNext := cur.next
	newNode := &node{
		val:  e,
		next: cur.next,
		prev: cur,
	}
	curNext.prev = newNode
	dll.size++
}

func (dll *DoublyLinkedList) AddFirst(e interface{}) {
	nextNode := dll.dummyHead.next

	newNode := &node{
		val:  e,
		next: nextNode,
		prev: dll.dummyHead,
	}

	nextNode.prev = newNode
	dll.dummyHead.next = newNode
	dll.size++
}

func (dll *DoublyLinkedList) AddLast(e interface{}) {
	preNode := dll.dummyTail.prev

	newNode := &node{
		val:  e,
		next: dll.dummyTail,
		prev: preNode,
	}

	preNode.next = newNode
	dll.dummyTail.prev = newNode
	dll.size++
}

func (dll *DoublyLinkedList) rangeCheckIndex(index int) {
	if index < 0 || index > dll.size {
		panic("index is out of index")
	}
}

func (dll *DoublyLinkedList) getMid() int {
	return dll.size / 2
}

// 获取索引为index的元素的值
func (dll *DoublyLinkedList) GetIndex(index int) interface{} {
	return dll.get(index).val
}

func (dll *DoublyLinkedList) RemoveIndex(index int) interface{} {
	targetNode := dll.get(index)
	targetNode.next.prev = targetNode.prev
	targetNode.prev.next = targetNode.next
	dll.size--
	return targetNode.val
}

// 判断链表是否为空
func (dll *DoublyLinkedList) Empty() bool {
	return dll.size == 0
}

// 获取链表的大小
func (dll *DoublyLinkedList) Size() int {
	return dll.size
}

// 移除索引为index的元素
func (dll *DoublyLinkedList) get(index int) *node {
	dll.rangeCheckIndex(index)
	mid := dll.getMid()
	if index >= mid {
		// 从后向前遍历
		cur := dll.dummyTail
		for i := dll.size; i > index; i-- {
			cur = cur.prev
		}
		return cur
	}
	// 从前向后遍历
	cur := dll.dummyHead.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	return cur
}

func (dll *DoublyLinkedList) String() string {
	buffer := bytes.Buffer{}
	cur := dll.dummyHead.next
	for cur.val != nil {
		buffer.WriteString(fmt.Sprint(cur.val) + "->")
		cur = cur.next
	}
	buffer.WriteString("nil")

	return buffer.String()
}
